<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>30. 串联所有单词的子串</title>
  </head>
  <body>
    <script>
      //     给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

      // 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

      //

      // 示例 1：

      // 输入：s = "barfoothefoobarman", words = ["foo","bar"]
      // 输出：[0,9]
      // 解释：
      // 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
      // 输出的顺序不重要, [9,0] 也是有效答案。
      // 示例 2：

      // 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
      // 输出：[]
      // 示例 3：

      // 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
      // 输出：[6,9,12]

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

      /**
       * @param {string} s
       * @param {string[]} words
       * @return {number[]}
       */
      var findSubstring = function (s, words) {
        if (words.length === 0) return []
        const wordLen = words[0].length // 记录 words 数组内每一单词的长度
        const strWindow = wordLen * words.length // 记录 words 数组内单词的总长度
        let i = 0 // s 字符串的索引
        const sLen = s.length // s 字符串的长度
        const arr = [] // 结果数组
        while (i <= sLen - strWindow) {
          let strChild = s.slice(i, i + strWindow) // 从 s 字符串截取 strWindow 长度的子串 strChild
          let test = true // 默认截取的字串 strChild 符合条件
          for (const val of words) {
            // 遍历 words 数组
            let n = accordIndex(strChild, val, wordLen) // 调用函数寻找 val 在字串 strChild 中合适的索引值
            if (n === -1) {
              // 存在不匹配单词，不符合条件，跳出 for of 循环
              test = false
              break
            } else {
              // 单词匹配，将其在子串 strChild 的位置上删除
              const shortArr = strChild.split('')
              shortArr.splice(n, wordLen)
              strChild = shortArr.join('')
            }
          }
          if (test) {
            // 当前子串 strChild 符合条件，添加索引值
            arr.push(i)
          }
          i++
        }
        return arr
      }

      /**
       * @param {string} str // 子串
       * @param {string[]} val // 单词
       * @param {number} len // 单词长度
       * @return {number} // 找到合适的索引值
       */
      function accordIndex(str, val, len) {
        let index = str.indexOf(val) // 记录 val 在子串 strChild 的索引位置
        if (index === -1) {
          // val 不在子串 strChild 中
          return -1
        }
        do {
          if (index === 0 || index % len === 0) {
            // val 的索引位需要为 0 或者 len 的倍数才返回
            break
          }
          index = str.indexOf(val, index + 1) // 继续寻找下一个索引值
        } while (index !== -1)
        return index
      }

      const res = findSubstring('ababaab', ['ab', 'ba', 'ba'])
      console.log(res)
    </script>
  </body>
</html>
